/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) 
{
        //
   struct Node*cur = head;
    while(cur)
    {
        // 在原节点你后插入新节点
        struct Node * copy = (struct Node * )malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur =   copy->next;
    }
    // 处理新节点的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;
        cur = copy->next;
    }
// 还原原链表，拆分拷贝链表
    struct Node* copyhead = NULL,* copytail = NULL;
    cur = head;
    while(cur)
    {
        struct Node*copy = cur->next;
        struct Node*next = copy->next;

        if(copytail == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copy;
        }
        cur->next = next;
        cur = next;
    }
    // 返回拷贝后的链表头地址
    return copyhead;
}



